/*
 * @lc app=leetcode.cn id=224 lang=golang
 *
 * [224] 基本计算器
 */

// @lc code=start

// 此题实现方式是通用方式，加减乘除都可以
import (
	"fmt"
	"strconv"
	"strings"
)

// 后缀表达式求值，逆波兰式
func calculate(s string) int {
	ss := toPolanString(s)
	// fmt.Println(ss)
	return getResult(ss)
}

// 后缀表达式的求解
// 从左到右依次入栈，如果碰见计算符号，则栈顶两个元素出栈进行计算
func getResult(s []string) int {
	n := len(s)
	stack := make([]int, 0, n)
	for _, v := range s {
		// fmt.Println(stack)
		if v != "+" && v != "-" && v != "*" && v != "/" {
			num, _ := strconv.Atoi(v)
			stack = append(stack, num)
		} else {
			if len(stack) == 1 {
				// 如果存在负数
				if v == "-" {
					stack[0] = -stack[0]
				}
			} else {
				num := calc(stack[len(stack)-2], stack[len(stack)-1], v)
				stack = stack[:len(stack)-2]
				stack = append(stack, num)
			}

		}
	}
	return stack[0]
}

func calc(a, b int, c string) int {
	switch c {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	case "/":
		return a / b
	}
	return 0
}

// 将表达式转换为后缀表达式，即逆波兰式
func toPolanString(s string) []string {
	n := len(s)
	stack := make([]byte, 0, n)
	polanString := make([]string, 0, n)
	// 设置优先级
	prior := make(map[byte]int)
	prior['('] = 3
	prior[')'] = 3
	prior['+'] = 1
	prior['-'] = 1
	prior['*'] = 2
	prior['/'] = 2

	for i := 0; i < n; i++ {
		if s[i] == ' ' {
			// i++
			continue
		}
		if s[i] >= '0' && s[i] <= '9' {
			var tmpNum strings.Builder
			for i < n {
				if s[i] >= '0' && s[i] <= '9' {
					tmpNum.WriteByte(s[i])
					i++
				} else {
					break
				}
			}
			i--
			polanString = append(polanString, tmpNum.String())
		} else if s[i] == '(' {
			stack = append(stack, s[i])
			// fmt.Println(string(stack))

		} else if s[i] == ')' {
			j := len(stack) - 1
			for ; j >= 0; j-- {
				if stack[j] != '(' {
					polanString = append(polanString, string(stack[j]))
				} else {
					break
				}
			}
			fmt.Println(i, j, string(stack), len(stack))
			stack = stack[:j]

		} else {
			if len(stack) == 0 {
				stack = append(stack, s[i])
			} else {

				// 栈顶出栈，直到比当前优先级更低，之后当前计算符加入
				v1, _ := prior[s[i]]
				v2, _ := prior[stack[len(stack)-1]]
				for v1 <= v2 {
					if len(stack) <= 0 || stack[len(stack)-1] == '(' {
						break
					}
					polanString = append(polanString, string(stack[len(stack)-1]))
					stack = stack[:len(stack)-1]
					if len(stack) <= 0 || stack[len(stack)-1] == '(' {
						break
					}
					v2, _ = prior[stack[len(stack)-1]]
				}

				stack = append(stack, s[i])
			}
		}

	}
	for len(stack) != 0 {
		polanString = append(polanString, string(stack[len(stack)-1]))
		stack = stack[:len(stack)-1]
	}
	return polanString
}

// @lc code=end
